Transactions on Combinatorics
Volume:13 Issue: 2, Jun 2024

Let $G$ be a simple graph, and $\vec{G}$ be an oriented graph of $G$ with an orientation and skew-adjacency matrix $S(\vec{G})$. Let $\lambda_1(\vec{G}), \lambda_2(\vec{G}),\ldots,\lambda_n(\vec{G})$ be the eigenvalues of $S(\vec{G})$. The number $\sum_{i=1}^{n}\lambda_i^k(\vec{G})$ $(k=0, 1,\ldots,n-1)$, denoted by $T_k(\vec{G})$, is called the $k$-th {\em skew spectral moment} of $\vec{G}$, and $T(\vec{G})=(T_0(\vec{G}),T_1(\vec{G}),\ldots,$ $T_{n-1}(\vec{G}))$ is the sequence of skew spectral moments of $\vec{G}$. Suppose $\vec{G}_1$ and $\vec{G}_2$ are two digraphs. We shall write $\vec{G}_1\prec_T \vec{G}_2$ ($\vec{G}_1$ comes before $\vec{G}_2$ in a $T$-order) if for some $k$ $(1 \leq k \leq n-1)$, $T_i(\vec{G}_1)=T_i(\vec{G}_2)$ ($i=0, 1,\ldots,k-1$) and $T_k(\vec{G_1})< T_k(\vec{G}_2)$ hold. For two given positive integers $p$ and $q$ with $p \leq q$, we denote $\mathscr T_{n}^{p,q}=\{T: T$ is a tree of order $n$ with a $(p,q)$-bipartition $\}$. In this paper, we discuss $T$-order among all trees in $\mathscr T_{n}^{p,q}$. Furthermore, the last three trees, in the $T$-order, underlying graphs among $\mathscr T_{n}^{p,q}~(4\leq p\leq q)$ are characterized.

In this paper, we establish a new $q$-analogue of the binomial identity:\begin{align*}&\sum_{k}(-1)^k{2n\choose n+3k}=\begin{cases}1,&\text{if $n=0$,}\\[5pt]2\cdot3^{n-1},&\text{if $n\ge 1$.}\end{cases}\end{align*}Our proof relies on a weight-preserving and sign-reversing involution due to Guo and Zhang.

This paper studies the non-progressive spread of influence with threshold model in social networks. Consider a graph $G$ with a threshold function $\tau$ on its vertex set. Spread of influence is a discrete dynamic process as follows. For a given set of initially infected vertices at time step $0$ each vertex $v$ gets infected at time step $i$, $i\geq1$, if and only if the number of infected neighbors are at least $\tau(v)$ in time step $i-1$. Our goal is to find the minimum cardinality of initially infected vertices (perfect target set) such that eventually all of the vertices get infected at some time step $\ell$. In this paper an upper bound for the convergence time of the process is given for graphs with general thresholds. Then an integer linear programming for the size of minimum perfect target set is presented. Then we give a lower bound for the size of perfect target sets with strict majority threshold on graphs which all of the vertices have even degrees. It is shown that the later bound is asymptotically tight.

Presenting sporadic simple groups as an automorphism groups of designs and graphs is an exciting field in finite group theory.In this paper, with two different methods, we present some new resolvable simple $3$-designs with Higman-Sims sporadic simple group $\rm HS$ as the full automorphism group.Also, we classify all block-transitive self-orthogonal designs on 176 points with even block size that admit sporadic simple group $\rm HS$ as an automorphism group. Furthermore, with these methods we construct some new resolvable $3$-designs on 36, 40, 120 and 176 points.

In this note we characterize all graphs without a $2C_3$-minor. A consequence of this result is a characterization of the bicircular matroids with no $U_{3,6}$-minor.

The Dowling lattice $Q_n(G)$, $G$ a finite group, generalizes the geometric lattice generated by all vectors, over a field, with at most two nonzero components. Abstractly, it is a fundamental object in the classification of finite matroids. Constructively, it is the frame matroid of a certain gain graph known as $G K{_n}{^V}$. Its Whitney numbers of the first kind enter into several important formulas. Ravagnani suggested and partially proved that these numbers of $Q_n(G)$ and higher-weight generalizations are polynomial functions of $|G|$. We give a simple proof for $Q_n(G)$ and its generalization to a wider class of gain graphs and biased graphs, and we determine the degrees and coefficients of the polynomials.

Let $G=(V,E)$\ be a simple graph and $f:V\rightarrow\{0,1,2,3\}$ be a function. A vertex $u$ with $f\left( u\right) =0$ is called an undefended vertex with respect to $f$ if it is not adjacent to a vertex $v$ with $f(v)\geq2.$ We call the function $f$ a generous Roman dominating function (GRDF) if for every vertex with $f\left( u\right) =0$ there exists at least a vertex $v$ with $f(v)\geq2$ adjacent to $u$ such that the function $f^{\prime}:V\rightarrow \{0,1,2,3\}$, defined by $f^{\prime}(u)=\alpha$, $f^{\prime}(v)=f(v)-\alpha$ where $\alpha=1$ or $2$, and $f^{\prime}(w)=f(w)$ if $w\in V-\{u,v\}$ has no undefended vertex. The weight of a generous Roman dominating function $f$ is the value $f(V)=\sum_{u\in V}f(u)$. The minimum weight of a generous Roman dominating function on a graph $G$\ is called the generous Roman domination number of $G$, denoted by $\gamma_{gR}\left( G\right) $. In this paper, we initiate the study of generous Roman domination and show its relationships. Also, we give the exact values for paths and cycles. Moreover, we present an upper bound on the generous Roman domination number, and we characterize cubic graphs $G$ of order $n$ with $\gamma_{gR}\left( G\right) =n-1$, and a Nordhaus-Gaddum type inequality for the parameter is also given. Finally, we study the complexity of this parameter.